package leetCode.offer57_ii;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
 * 序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
 *
 * 示例 1：
 * 输入：target = 9
 * 输出：[[2,3,4],[4,5]]
 *
 * 示例 2：
 * 输入：target = 15
 * 输出：[[1,2,3,4,5],[4,5,6],[7,8]]
 *
 * 限制：
 * 1 <= target <= 10^5
 */
public class Solution1 implements Solution{


    @Override
    public int[][] findContinuousSequence(int target) {
        int start = 1;
        int end = 2;
        int sum = 3;
        List<int[]> result = new ArrayList<>();

        for(int i=0;i<target;i++){
            if(sum<target){
                end++;
                sum+=end;
            }
            else if(sum>target){
                sum-=start;
                start++;
            }
            else{
                List<Integer> item = new ArrayList<>();
                for(int n=start;n<=end;n++){
                    item.add(n);
                }
                result.add(item.stream().mapToInt(Integer::valueOf).toArray());
                end++;
                sum+=end;
            }
        }

        return result.toArray(new int[0][]);
    }

    public static void main(String[] args) {
        Solution1 solution1 = new Solution1();
        System.out.println(Arrays.toString(solution1.findContinuousSequence(9)));
    }
}
